\section{Experimental Evaluation}
\label{sec:experiments}

\newcommand{\scale}{0.35}

% Notes from June 16th meeting:

% Emphasize that ratio doesn't grow too much with k (in theory up to k, in practice 2 or 3) DONE

% Fewer k's for CDF. Explain well (close to 1 is good).  

% show one example where m is not known (and argue that it will be similar) DONE

% Random order likely to hurt us -- remove nice features that fixed order. DONE

% Would like to try on ``real'' graphs eventually

% (Change ``density ratio'' to something like ``density approximation ratio'') 

% Only show a few for running time and others (condMat - sparse, HepPh - dense, Enron - middle)

% Say that max ratio goes to 3 for AS graph  

% Show all graphs for average




% State goals of section and system experiments were run on

We evaluated the performance of our algorithm on a number of real data
sets. The results in this section demonstrate that our algorithm gives
a substantial speedup in running time for a small cost in the
estimation quality of the desity of the densest subgraph. All our code
was written in C++ and run on an Intel Core 2 Duo machine running
Ubuntu 12.04.2.

% Description of data sets

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
GraphName    &   nodes &  edges  &  approx. density\\
\hline \hline
as20000102   &   6474  &  13895  &  9.229  \\
ca-GrQc      &   5242  &  14496  &  22.391 \\
ca-HepTh     &   9877  &  25998  &  15.5   \\
ca-CondMat   &   23133 &  93497  &  12.615 \\
ca-HepPh     &   12008 &  118521 &  119.004\\
email-Enron  &   36692 &  183831 &  37.344 \\
ca-AstroPh   &   18772 &  198110 &  29.563 \\
\hline
\end{tabular}
\caption{Data Sets}
\label{tab:datasets}
\end{center}
\end{table}


We used a number of large network data sets freely available from the
Stanford Network Analysis Project
(SNAP)\footnote{https://snap.stanford.edu}. The key statistics of
these data sets are summarized in Table~\ref{tab:datasets}. These data
sets were large enough that it would be prohibitively expensive (in
terms of running time) to compute their densest subgraphs exactly,
hence the approximate densities estimated using Charikar's linear-time
2-approximation algorithm~\cite{Charikar00} are reported in the
table. In comparison with exact results for some of the smaller
graphs, it turns out that this algorithm gives an estimate that is
fairly close to the actual value in practice (see, e.g. \cite{BahmaniKV12})\danupon{\cite{BahmaniKV12} is not the best one to cite here. I cited it because I don't have time to find a more proper one (which we came across at some point)}.


% Algorithms compared

There is no known prior work on computing the densest subgraph in the dynamic setting. As a baseline of comparison with our algorithm, we ran the
Charikar algorithm after the insertion of each edge. This allows us to
compare the result of our algorithm with the (near-)exact answer at
each insertion; we do not, however, claim this to be a viable method
for approximating the densest subgraph\danupon{I'm confused by this sentence. Why do we have to say this?}. Indeed, as will be
demonstrated shortly, it turns out that this method is several orders
of magnitude slower than our algorithm, sometimes taking days of
processing time to run in practice.

% Some details about our algorithm

\begin{figure}
\begin{center}
\includegraphics[width=0.5\textwidth]{figs/knownvsunknownm-ca-AstroPh-varyk-avg.pdf}
\caption{Average density for known vs. unknown $m$ for ca-AstroPh}
\label{fig:knownvsunknownm}
\end{center}
\end{figure}

\danupon{I think we should change this sentence since we don't have a separate algorithm for the case known $m$ now. (Earlier we thought that it will be easier to write this algorithm first but it turns out that the case of unknown $m$ is also not too hard to analyze.)}
%
In all our experiments we consider one the case where one edge is inserted at a time (i.e. $p=m$) since this case highlights the worst-case performances of the algorithms. 
%
Recall that there are two versions of our algorithms (described in \Cref{sec:algo offline,sec:algo online}): when the number of edges,
$m$, is known or not known beforehand.
%
%When $m$ was not known
%beforehand, we initialized an estimate of its value to one hundred and
%doubled our estimate everytime it was exceeded. 
%
%We found the results to be similar 
Our experiments show that the results from both algorithms are similar
(e.g., see Figure~\ref{fig:knownvsunknownm}). Hence, we only show
results for when $m$ is known beforehand to simplify the presentation. We also investigated edge
insertion order, comparing the results when the edges were presented
in the original order (i.e., the order that they appear in the
respective data files) and randomly permuted order. In the latter case
we averaged the result over ten independent random permutations.

% RESULTS
\subsection{Results for original edge order}

% Running time comparison for varying bin size and naive

\begin{figure*}
\begin{center}
%\subfigure[as20000102]{\includegraphics[width=\scale\linewidth]{figs/time/as20000102-1402582868-varyk-TIME.pdf}}
%\subfigure[ca-GrQc]{\includegraphics[width=\scale\linewidth]{figs/time/ca-GrQc-1402583092-varyk-TIME.pdf}}
%\subfigure[ca-HepTh]{\includegraphics[width=\scale\linewidth]{figs/time/ca-HepTh-1402587711-varyk-TIME.pdf}}
\subfigure[ca-HepPh]{\includegraphics[width=\scale\linewidth]{figs/time/ca-HepPh-1402625501-varyk-TIME.pdf}}
\subfigure[ca-CondMat]{\includegraphics[width=\scale\linewidth]{figs/time/ca-CondMat-1402593811-varyk-TIME.pdf}}
\subfigure[email-Enron]{\includegraphics[width=\scale\linewidth]{figs/time/email-Enron-1402666193-varyk-TIME.pdf}}
%\subfigure[ca-AstroPh]{\includegraphics[width=\scale\linewidth]{figs/time/ca-AstroPh-1402781733-varyk-TIME.pdf}}
\end{center}
\caption{Running times (original order)}
\label{fig:time}
\end{figure*}

In this section we present the results of our algorithm for the case
that the edges are presented in the order given in the data. The edges
are presented in adjacency list order (i.e., all the edges connected
to the first node, followed by all the edges connected to the second
node, etc.). In the interest of space, we only show the results for
the following three graphs: ca-CondMat (sparse), ca-HepPh (dense), and
email-Enron (most nodes).

In Figure~\ref{fig:time} we compare the running time of our algorithm
against the running time for the naive baseline described above. These
plots show the our algorithm consistently give 2-3 orders of magnitude
speedup in all cases (note that the $y$-axis is in logscale). This
difference is due to the $O(m^2)$ running time cost of the baseline
compared with the $O(km^{1 + 1/k})$ time needed by our algorithm. For
instance, for $k = 2$ this is a difference of $O(m^2)$ versus
$O(m^{1.5})$, a considerable speedup when $m$ is large. Also note that
the running time decreases with $k$; however, there is little marginal
running time benefit for $k$ beyond 4 in practice. 

% Average density ratios for each bin size

\begin{figure*}
\begin{center}
%\subfigure[as20000102]{\includegraphics[width=\scale\linewidth]{figs/average/as20000102-1402582868-varyk-avg.pdf}}
%\subfigure[ca-GrQc]{\includegraphics[width=\scale\linewidth]{figs/average/ca-GrQc-1402583092-varyk-avg.pdf}}
%\subfigure[ca-HepTh]{\includegraphics[width=\scale\linewidth]{figs/average/ca-HepTh-1402587711-varyk-avg.pdf}}
\subfigure[ca-HepPh]{\includegraphics[width=\scale\linewidth]{figs/average/ca-HepPh-1402625501-varyk-avg.pdf}}
\subfigure[ca-CondMat]{\includegraphics[width=\scale\linewidth]{figs/average/ca-CondMat-1402593811-varyk-avg.pdf}}
\subfigure[email-Enron]{\includegraphics[width=\scale\linewidth]{figs/average/email-Enron-1402666193-varyk-avg.pdf}}
%\subfigure[ca-AstroPh]{\includegraphics[width=\scale\linewidth]{figs/average/ca-AstroPh-1402781733-varyk-avg.pdf}}
\end{center}
\caption{Average density approximation ratio (original order)}
\label{fig:avg}
\end{figure*}

\begin{figure*}
\begin{center}
\subfigure[as20000102]{\includegraphics[width=\scale\linewidth]{figs/maximum/as20000102-1402582868-varyk-max.pdf}}
%\subfigure[ca-GrQc]{\includegraphics[width=\scale\linewidth]{figs/maximum/ca-GrQc-1402583092-varyk-max.pdf}}
%\subfigure[ca-HepTh]{\includegraphics[width=\scale\linewidth]{figs/maximum/ca-HepTh-1402587711-varyk-max.pdf}}
\subfigure[ca-HepPh]{\includegraphics[width=\scale\linewidth]{figs/maximum/ca-HepPh-1402625501-varyk-max.pdf}}
\subfigure[ca-CondMat]{\includegraphics[width=\scale\linewidth]{figs/maximum/ca-CondMat-1402593811-varyk-max.pdf}}
\subfigure[email-Enron]{\includegraphics[width=\scale\linewidth]{figs/maximum/email-Enron-1402666193-varyk-max.pdf}}
%\subfigure[ca-AstroPh]{\includegraphics[width=\scale\linewidth]{figs/maximum/ca-AstroPh-1402781733-varyk-max.pdf}}
\end{center}
\caption{Maximum density approximation ratio (original order)}
\label{fig:max}
\end{figure*}

Figure~\ref{fig:avg} shows the average (arithmetical mean) ratio of
the density of our algorithm compared with that of the baseline
(2-approximation) algorithm. This ratio is under ten percent for small
$k$ values ($k \leq 4$, as mentioned above), and below 2-3\% for some
of the graphs. This shows that there is a very small loss in the
estimated density ratio from our algorithm compared with the
baseline. Put another way, we pay for the hundred-fold speedup of our
algorithm with only a small drop in estimation accuracy.

We also examined the worst ratio between our algorithm and the
baseline in each case (Figure~\ref{fig:max}). Intuitively, this
highlights the worst case performance of our algorithm across the
evolution of the entire sequence of updates. We begin to see more substantial
deviation here, with our algorithm giving approximation ratios of up
to 3 in some rare instances. Note, however, that even in the worst
case the result is considerably better than the worst-case bound of
$k$ for the $k$-bin algorithm.


% Show some density ratio distribution for one bin size

\begin{figure*}
\begin{center}
%\subfigure[as20000102]{\includegraphics[width=\scale\linewidth]{figs/cdf/as20000102-1402582868-varyk-cdf.pdf}}
%\subfigure[ca-GrQc]{\includegraphics[width=\scale\linewidth]{figs/cdf/ca-GrQc-1402583092-varyk-cdf.pdf}}
%\subfigure[ca-HepTh]{\includegraphics[width=\scale\linewidth]{figs/cdf/ca-HepTh-1402587711-varyk-cdf.pdf}}
\subfigure[ca-HepPh]{\includegraphics[width=\scale\linewidth]{figs/cdf/ca-HepPh-1402625501-varyk-cdf.pdf}}
\subfigure[ca-CondMat]{\includegraphics[width=\scale\linewidth]{figs/cdf/ca-CondMat-1402593811-varyk-cdf.pdf}}
\subfigure[email-Enron]{\includegraphics[width=\scale\linewidth]{figs/cdf/email-Enron-1402666193-varyk-cdf.pdf}}
%\subfigure[ca-AstroPh]{\includegraphics[width=\scale\linewidth]{figs/cdf/ca-AstroPh-1402781733-varyk-cdf.pdf}}
\end{center}
\caption{CDF of density approximation ratio (original order)}
\label{fig:cdf}
\end{figure*}


To give a better sense of the values taken by the ratio of our
algorithm to the baseline, we show the the cumulative density plot for
a few specific cases in Figure~\ref{fig:cdf}. This gives the entire
distribution of the ratio between the density of the naive solution to
that of our $k$-bin solution. A ratio near one means that our
algorithm is near-optimal. As can be seen in the figure, the ratio is
at or close to 1 almost all the time for $k = 2$, but deviates farther
as the value of $k$ increases. This is to be expected since we know
from our analysis that the theoretical approximation ratio increases
linearly with $k$.

\subsection{Results for random edge order}

% Show density ratio for random-order graph


\begin{figure*}
\begin{center}
%\subfigure[as20000102]{\includegraphics[width=\scale\linewidth]{figs/random/as20000102-1399154052-varyk-TIME.pdf}}
%\subfigure[ca-GrQc]{\includegraphics[width=\scale\linewidth]{figs/random/ca-GrQc-1399155931-varyk-TIME.pdf}}
%\subfigure[ca-HepTh]{\includegraphics[width=\scale\linewidth]{figs/random/ca-HepTh-1399215649-varyk-TIME.pdf}}
\subfigure[ca-HepPh]{\includegraphics[width=\scale\linewidth]{figs/random/ca-HepPh-1399561369-varyk-TIME.pdf}}
\subfigure[ca-CondMat]{\includegraphics[width=\scale\linewidth]{figs/random/ca-CondMat-1399231708-varyk-TIME.pdf}}
\subfigure[email-Enron]{\includegraphics[width=\scale\linewidth]{figs/random/email-Enron-1399818771-varyk-TIME.pdf}}
%\subfigure[ca-AstroPh]{\includegraphics[width=\scale\linewidth]{figs/random/ca-AstroPh-1401723858-varyk-TIME.pdf}}
\end{center}
\caption{Running times when edges were randomly ordered}
\label{fig:time-random}
\end{figure*}

\begin{figure*}
\begin{center}
%\subfigure[as20000102]{\includegraphics[width=\scale\linewidth]{figs/random/as20000102-1399154052-varyk-avg.pdf}}
%\subfigure[ca-GrQc]{\includegraphics[width=\scale\linewidth]{figs/random/ca-GrQc-1399155931-varyk-avg.pdf}}
%\subfigure[ca-HepTh]{\includegraphics[width=\scale\linewidth]{figs/random/ca-HepTh-1399215649-varyk-avg.pdf}}
\subfigure[ca-HepPh]{\includegraphics[width=\scale\linewidth]{figs/random/ca-HepPh-1399561369-varyk-avg.pdf}}
\subfigure[ca-CondMat]{\includegraphics[width=\scale\linewidth]{figs/random/ca-CondMat-1399231708-varyk-avg.pdf}}
\subfigure[email-Enron]{\includegraphics[width=\scale\linewidth]{figs/random/email-Enron-1399818771-varyk-avg.pdf}}
%\subfigure[ca-AstroPh]{\includegraphics[width=\scale\linewidth]{figs/random/ca-AstroPh-1401723858-varyk-avg.pdf}}
\end{center}
\caption{Average approximation ratio when edges were randomly ordered}
\label{fig:avg-random}
\end{figure*}

\begin{figure*}
\begin{center}
%\subfigure[as20000102]{\includegraphics[width=\scale\linewidth]{figs/random/as20000102-1399154052-varyk-max.pdf}}
%\subfigure[ca-GrQc]{\includegraphics[width=\scale\linewidth]{figs/random/ca-GrQc-1399155931-varyk-max.pdf}}
\subfigure[ca-HepTh]{\includegraphics[width=\scale\linewidth]{figs/random/ca-HepTh-1399215649-varyk-max.pdf}}
\subfigure[ca-HepPh]{\includegraphics[width=\scale\linewidth]{figs/random/ca-HepPh-1399561369-varyk-max.pdf}}
\subfigure[ca-CondMat]{\includegraphics[width=\scale\linewidth]{figs/random/ca-CondMat-1399231708-varyk-max.pdf}}
\subfigure[email-Enron]{\includegraphics[width=\scale\linewidth]{figs/random/email-Enron-1399818771-varyk-max.pdf}}
%\subfigure[ca-AstroPh]{\includegraphics[width=\scale\linewidth]{figs/random/ca-AstroPh-1401723858-varyk-max.pdf}}
\end{center}
\caption{Maximum approximation ratio when edges were randomly ordered}
\label{fig:max-random}
\end{figure*}

\begin{figure*}
\begin{center}
%\subfigure[as20000102]{\includegraphics[width=\scale\linewidth]{figs/random/as20000102-1399154052-varyk-cdf.pdf}}
%\subfigure[ca-GrQc]{\includegraphics[width=\scale\linewidth]{figs/random/ca-GrQc-1399155931-varyk-cdf.pdf}}
%\subfigure[ca-HepTh]{\includegraphics[width=\scale\linewidth]{figs/random/ca-HepTh-1399215649-varyk-cdf.pdf}}
\subfigure[ca-HepPh]{\includegraphics[width=\scale\linewidth]{figs/random/ca-HepPh-1399561369-varyk-cdf.pdf}}
\subfigure[ca-CondMat]{\includegraphics[width=\scale\linewidth]{figs/random/ca-CondMat-1399231708-varyk-cdf.pdf}}
\subfigure[email-Enron]{\includegraphics[width=\scale\linewidth]{figs/random/email-Enron-1399818771-varyk-cdf.pdf}}
%\subfigure[ca-AstroPh]{\includegraphics[width=\scale\linewidth]{figs/random/ca-AstroPh-1401723858-varyk-cdf.pdf}}
\end{center}
\caption{CDF of approximation ratios when edges were randomly ordered}
\label{fig:cdf-random}
\end{figure*}


In this section we will show the results for random ordering.  For all
the earlier experiments, we streamed the edges of the graph in the
original order, i.e., the order in which they appeared in the data
files. Since it is possible that there were artifacts introduced by
this specific ordering, we also ran the algorithms when the edge order
was randomly permuted. We expected to see the approximation ratios
degrade as the algorithms could no longer take advantage of the fixed
ordering of edges. All results are the average of ten independent runs.

The results for running times is shown in
Figure~\ref{fig:time-random}. We once again see a 2-3 order magnitude
speedup in running time for the $k$-bin algorithm, even for smaller
values of $k$. Once again, there is very little marginal benefit from
increasing $k$ beyond four. 

In Figures~\ref{fig:avg-random} and~\ref{fig:max-random} we see the
average and maximum density approximation ratios for the graphs in
random order.  Once again, the average ratio was below 10\% for small
$k$.  In most cases the maximum ratios were within 2 and always under
2 for $k \leq 4$.  In comparison with Figure~\ref{fig:avg}
and~\ref{fig:max}, we can see a slight decrease in approximation
fidelity. Note once again that these values are considerably lower
than the worst-case bounds of the $k$-bin algorithm.  Finally, we show
the full distribution of ratios in the random order case in
Figure~\ref{fig:cdf-random}. Once again, $k = 2$ gives a very good
approximation ratio, and the ratio increases as $k$ increases.


{\bf Experiment summary:} We observed a 2-3 order of magnitude speedup
of our algorithm compared with the naive baseline (of re-computing the
density after each edge insertion). This speedup was achieved for
small values of $k$ ($k < 5$). The cost of the speedup in running time
was a small degradation of the approximation ratio. Though in the
worst cases the approximation ratio could be as large as 2 or 3, in
the average case (and most of the time) it was close to 1. Using a
small value of $k$ (between 2 and 4, depending on speed/accuracy
trade-off) seems to give the the best results.
